#include <vector>
using namespace std;
class NumMatrix
{
public:
    NumMatrix(vector<vector<int>> &matrix)
        : add(matrix.size() + 1)
    {
        add[0].resize(matrix[0].size() + 1);
        for (int i = 1; i < add.size(); i++)
        {
            add[i].resize(matrix[i - 1].size() + 1);
        }
        for (int i = 1; i < add.size(); i++)
        {
            for (int j = 1; j < add[0].size(); j++)
            {
                add[i][j] = add[i][j - 1] + matrix[i - 1][j - 1];
            }
        }
    }

    int sumRegion(int row1, int col1, int row2, int col2)
    {
        long long sum = 0;
        for (int i = row1; i <= row2; i++)
        {
            sum += add[i + 1][col2 + 1] - add[i + 1][col1];
        }
        return sum;
    }

private:
    vector<vector<int>> add;
};

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix* obj = new NumMatrix(matrix);
 * int param_1 = obj->sumRegion(row1,col1,row2,col2);
 */